package leetcode.editor.cn;

import leetcode.editor.cn.ListNode;

////给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
////
////
////
////
////
////
//// 示例 1：
////
////
////输入：head = [4,2,1,3]
////输出：[1,2,3,4]
////
////
//// 示例 2：
////
////
////输入：head = [-1,5,3,4,0]
////输出：[-1,0,3,4,5]
////
////
//// 示例 3：
////
////
////输入：head = []
////输出：[]
////
////
////
////
//// 提示：
////
////
//// 链表中节点的数目在范围 [0, 5 * 10⁴] 内
//// -10⁵ <= Node.val <= 10⁵
////
////
////
////
//// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
////
//// Related Topics 链表 双指针 分治 排序 归并排序 👍 2177 👎 0
//
//package leetcode.editor.cn;
////java:排序链表
public class Q0148SortList {
    public static void main(String[] args){
        Solution solution = new Q0148SortList().new Solution();
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        solution.sortList(head);
    }
//    //leetcode submit region begin(Prohibit modification and deletion)
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
class Solution {
    public ListNode sortList(ListNode head) {
        ListNode newHead = new ListNode(-1);

        ListNode cur = head;
        ListNode minValNode = new ListNode(Integer.MAX_VALUE);
        while (head != null) {
            while (cur != null) {
                if (minValNode.val > cur.val) {
                    minValNode = cur;
                }
                cur = cur.next;
            }

            newHead.next = minValNode;
        }
        return newHead.next;
    }
}
////leetcode submit region end(Prohibit modification and deletion)
//
}